class Solution {
    int m, n;
    vector<vector<bool>> visited;   // 记录哪些坐标已经使用过了，防止走重复路径
    vector<pair<int, int>> dir = { {0, -1}, {0, 1}, {1, 0}, {-1, 0} };      // 四个方向
    bool dfs(vector<vector<char>>& board, int i, int j, string &word, int pos)
    {
        // 因为每次都是匹配成功了才往后匹配下一个字符
        // 如果有幸走到这里，说明前面都匹配成功，返回true
        if(pos == word.size())
            return true;

        for(int k = 0; k < 4; k++)
        {
            // 枚举上下左右下标
            // 判断是否合法，并且没有被匹配过，并且该下标的字符和word的当前字符相匹配，此时再递归下一个位置
            int x = dir[k].first + i, y = dir[k].second + j;
            if(x >= 0 && x < m && y >= 0 && y < n && visited[x][y] == false && board[x][y] == word[pos])
            {
                visited[x][y] = true;
                if(dfs(board, x, y, word, pos + 1))
                    return true;
                // 恢复现场
                visited[x][y] = false;
            }
        }
        return false;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size(), n = board[0].size();
        visited = vector<vector<bool>>(m, vector<bool>(n));
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                // 在这里先枚举第一个正确匹配的位置
                if(board[i][j] == word[0])
                {
                    visited[i][j] = true;
                    if(dfs(board, i, j, word, 1))
                        return true;
                    // 恢复现场
                    visited[i][j] = false;
                }
            }
        }
        // 如果上面循环没有return，说明要么有可能第一个字符都不能正确匹配，要么第一个字符正确匹配但是后面匹配不成功
        // 直接return false
        return false;
    }
};